package 六查找;

import 五排序.RadixSort;

import java.util.ArrayList;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/23 10:01
 * 插值排序
 */
public class InsertValueSearch {
    private static ArrayList index = new ArrayList();

    public static void main(String[] args) {

        int i = 10;
        int[] array = new int[i];
        //生成随机排序
        for (int k = 0; k < 10; k++) {

            for (int j = 0; j < i; j++) {
                array[j] = (int) (Math.random() * i * 1);
            }

            //原本数组：
            System.out.printf("第%d \t次数组=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            //开始排序
            RadixSort.radixSort(array);

            //输出
            System.out.printf("，排序后为=》   ", (k + 1));
            for (int i1 : array) {
                System.out.print(i1 + " \t");
            }
            System.out.println();
            int value = (int) (Math.random() * i * 1);
            ArrayList list = insertValueSearch(array, value, 0, array.length - 1);
            System.out.println(list.toString() + "  查找的值为  " + value);
            //重置列表
            index = new ArrayList();
        }

    }

    public static ArrayList insertValueSearch(int[] array, int value, int left, int right) {
        if (left > right || array[left] > value || array[right] < value) {
            //没找到
            return index;
        } else {
            //插值排序的算法 就是自适应值
            int mid = left + (right - left) * (value - array[left]) / (array[right] - array[left]);
            if (array[mid] == value) {

                index.add(mid);

                for (int i = mid + 1; i <= right; i++) {
                    if (array[i] == value) {
                        index.add(i);
                    } else {
                        break;
                    }
                }
                for (int i = mid - 1; i >= left; i--) {
                    if (array[i] == value) {
                        index.add(i);
                    } else {
                        break;
                    }
                }
                //返回下标
                return index;
            } else if (array[mid] > value) {
                return insertValueSearch(array, value, left, mid - 1);
            } else {
                return insertValueSearch(array, value, mid + 1, right);
            }
        }

    }

}
